package own.stu.jobgib.playown.alg.leetcode.editor.cn;

//一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出
//这个数字。 
//
// 
//
// 示例 1: 
//
// 输入: [0,1,3]
//输出: 2
// 
//
// 示例 2: 
//
// 输入: [0,1,2,3,4,5,6,7,9]
//输出: 8 
//
// 
//
// 限制： 
//
// 1 <= 数组长度 <= 10000 
// Related Topics 数组 二分查找 
// 👍 125 👎 0



public class QueShiDeShuZiLcof{
    public static void main(String[] args) {
        Solution solution = new QueShiDeShuZiLcof().new Solution();
        System.out.println(solution.missingNumber(new int[]{0}));
        System.out.println(solution.missingNumber(new int[]{0, 1,2,3}));
        System.out.println(solution.missingNumber(new int[]{1,2,3}));
        System.out.println(solution.missingNumber(new int[]{0,1,3}));
        System.out.println(solution.missingNumber(new int[]{0,1,2,3,4,5,6,7,9}));

    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int missingNumber(int[] nums) {
            if (nums == null || nums.length <= 0) {
                return -1;
            }
            int l = 0;
            int r = nums.length - 1;
            int m = 0;
            while(l + 1 < r){
                m = (r - l) / 2 + l;
                if(m < nums[m]){
                    r = m;
                }else{
                    l = m;
                }
            }

            if(l < nums[l]) return l;
            else if(r < nums[r]) return r;
            return nums.length;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
